In a communications network it is usually desirable that stations, or nodes, in the network "know" the addresses of their neighbors, i.e. the other stations with which they can communicate directly. It is particularly important that routers contain this information, so that they can efficiently direct messages along paths leading to the message destinations. Each station can be configured manually with the addresses of other stations with which it directly communicates. However this does not provide for the efficient configuration of stations having large numbers, for example, hundreds of neighbors. Nor does it provide for the efficient inclusion of additional stations or the removal of stations from the system.
In a network or subnetwork that employs a broadcast transmission medium, each station can use a multicast message to identify itself to all of its neighbors. With this arrangement each station can maintain an accurate list of all of its neighbors.
However, a corresponding arrangement on a non-broadcast medium would require an unduly large number of station-identifying messages. Accordingly a different system has been proposed for such media.
One station is selected as a designated station, e.g. on the basis of a priority, such as high or low identification number as compared with the identification of its neighbors. All the other stations periodically send to the designated station Is-Hello messages identifying themselves to the designated station. The designated station maintains an address list of all of the neighboring stations and periodically communicates this list to each of them in Dn-Hello messages.
Each station is initially configured with a list containing the address of at least one other station in its neighborhood. At system startup, or if a designated station goes out of service, each other station initially assumes that it is the designated station and it sends Dn-Hello messages to each of the stations on its list. It also receives Hello messages from other stations. If it receives a Hello message from a station having a hiker priority than the station it currently "believes" is the designated station (which may be itself), it assumes that the sender is the designated station, it ceases sending Dn-Hello messages and begins to send Is-Hello messages to the latter station.
If a station receives a message from a second station, but believes that a third station is the designated station, it sends a Hello-Redirect message to the second station, advising the latter that the third station is the designated station. This protocol will ultimately result in the selection of a single designated station.
When a station is installed in the network, the foregoing protocol will ultimately result in an identification of the designated station to the new station and the inclusion of the new station on the list that is communicated to the other stations by the designated station.
In the present application we use the term Hello to refer collectively to the three types of messages described above.
Moreover, since the protocols involved herein relate to multi-access links, we refer to addresses on the multi-access links as "data link" addresses.
While the systems discussed above provide efficient mechanisms for the incorporation of additional stations into a network, they are subject to compromise by an intruder who manages to connect an alien station into the network. The alien station will be recognized as a legitimate neighboring station and will thus provide unauthorized access to the network. Indeed, in a system employing the Hello message protocol, an eavesdropper who knows the selection criterion for a designated station can, in some networks, provide an alien station with an address that causes it to become the designated station. The intruder can then wreak havoc by removing legitimate stations from the address list and/or adding other alien stations.
The principal object of the invention is therefore to prevent the insertion of unauthorized stations into a network. Specifically, it is an object of the invention to provide a system in which only legitimate stations incorporated into the system will be recognized for communications from and to neighboring stations.